Search for: All records

We give an overview of the 2021 Computational Geometry Challenge, which targeted the problem of optimally coordinating a set of robots by computing a family of collision-free trajectories for a set S of n pixel-shaped objects from a given start configuration to a desired target configuration. 

We give an overview of theoretical and practical aspects of finding a simple polygon of minimum ( Min-Area ) or maximum ( Max-Area ) possible area for a given set of n points in the plane. Both problems are known to be NP -hard and were the subject of the 2019 Computational Geometry Challenge, which presented the quest of finding good solutions to more than 200 instances, ranging from n = 10 all the way to n = 1, 000, 000. 

We investigate algorithmic approaches for targeted drug delivery in a complex, maze-like environment, such as a vascular system. The basic scenario is given by a large swarm of micro-scale particles ("agents") and a particular target region ("tumor") within a system of passageways. Agents are too small to contain on-board power or computation and are instead controlled by a global external force that acts uniformly on all particles, such as an applied fluidic flow or electromagnetic field. The challenge is to deliver all agents to the target region with a minimum number of actuation steps. We provide a number of results for this challenge. We show that the underlying problem is NP-hard, which explains why previous work did not provide provably efficient algorithms. We also develop a number of algorithmic approaches that greatly improve the worst-case guarantees for the number of required actuation steps. We evaluate our algorithmic approaches by a number of simulations, both for deterministic algorithms and searches supported by deep learning, which show that the performance is practically promising. 

We present algorithmic results for the parallel assembly of many micro-scale objects in two and three dimensions from tiny particles, which has been proposed in the context of programmable matter and self-assembly for building high-yield micro-factories. The underlying model has particles moving under the influence of uniform external forces until they hit an obstacle. Particles bond when forced together with another appropriate particle. Due to the physical and geometric constraints, not all shapes can be built in this manner; this gives rise to the Tilt Assembly Problem (TAP) of deciding constructibility. For simply-connected polyominoes P in 2D consisting of N unit-squares (“tiles”), we prove that TAP can be decided in 𝑂(𝑁log𝑁) time. For the optimization variant MaxTAP (in which the objective is to construct a subshape of maximum possible size), we show polyAPX-hardness: unless P = NP, MaxTAP cannot be approximated within a factor of Ω(𝑁13) ; for tree-shaped structures, we give an Ω(𝑁12) -approximation algorithm. For the efficiency of the assembly process itself, we show that any constructible shape allows pipelined assembly, which produces copies of P in O(1) amortized time, i.e., N copies of P in O(N) time steps. These considerations can be extended to three-dimensional objects: For the class of polycubes P we prove that it is NP-hard to decide whether it is possible to construct a path between two points of P; it is also NP-hard to decide constructibility of a polycube P. Moreover, it is expAPX-hard to maximize a sequentially constructible path from a given start point. 

This paper introduces techniques for mosquito population surveys in the field using electrified screens (bug zappers) mounted to a UAV. Instrumentation on the UAV logs the UAV path and the GPS location, altitude, and time of each mosquito elimination. Hardware experiments with a UAV equipped with an electrified screen provide real-time measurements of (former) mosquito locations and mosquito-free volumes. Planning a trajectory for the UAV that maximizes the number of mosquito kills is related to the Traveling Salesman Problem, the Lawn Mower Problem and, most closely, Milling with Turn Cost. We reduce this problem to considering variants of covering a grid graph with minimum turn cost, corresponding to optimized energy consumption. We describe an exact method based on Integer Programming that is able to compute provably optimal instances with over 1,500 pixels. These solutions are then implemented on the UAV. 

We propose an approach to mapping tissue and vascular systems without the use of contrast agents, based on moving and measuring magnetic particles. To this end, we consider a swarm of particles in a 1D or 2D grid that can be tracked and controlled by an external agent. Control inputs are applied uniformly so that each particle experiences the same applied forces. We present algorithms for three tasks: (1) Mapping, i.e., building a representation of the free and obstacle regions of the workspace; (2) Subset Coverage, i.e., ensuring that at least one particle reaches each of a set of desired locations; and (3) Coverage, i.e., ensuring that every free region on the map is visited by at least one particle. These tasks relate to a large body of previous work from robot navigation, both from theory and practice, which is based on individual control. We provide theoretical insights that have potential relevance for fast MRI scans with magnetically controlled contrast media. In particular, we develop a fundamentally new approach for searching for an object at an unknown distance D, where the search is subject to two different and independent cost parameters for moving and for measuring. We show that regardless of the relative cost of these two operations, there is a simple O(log D/log log D)-competitive strategy, which is the best possible. Also, we provide practically useful and computationally efficient strategies for higher-dimensional settings. These algorithms extend to any number of particles and show that additional particles tend to reduce the mean and the standard deviation of the time required for each task. 

We present results arising from the problem of sweeping a mosquito-infested area with an Un-manned Aerial Vehicle (UAV) equipped with an electrified metal grid. This is related to the Traveling Salesman Problem, the Lawn Mower Problem and, most closely, Milling with TurnCost. Planning a good trajectory can be reduced to considering penalty and budget variants of covering a grid graph with minimum turn cost. On the theoretical side, we show the solution of a problem from The Open Problems Project that had been open for more than 15 years, and hint at approximation algorithms. On the practical side, we describe an exact method based on Integer Programming that is able to compute provably optimal instances with over 500 pixels. These solutions are actually used for practical trajectories, as demonstrated in the video.